package com.sicheng.lc.周赛.分类.并差集;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/11 22:41
 */
@SuppressWarnings("all")
public class 元素值大于变化阈值的子数组 {
    //https://leetcode.cn/problems/subarray-with-elements-greater-than-varying-threshold/

    static int N = (int) 1e5;
    static int[] p = new int[N + 1];
    static int[] size = new int[N + 1];

    {
        Arrays.fill(size, 1);
        for (int i = 0; i < p.length; i++) {
            p[i] = i;
        }
    }

    int find(int x) {
        if (p[x] == x)
            return x;
        return p[x] = find(p[x]);
    }


    // 得到原素组的索引数组
    // 降序序排索引数组
    // 遍历 索引数组  这样就会顺着索引数组优先找到大的元素
    // 将索引 i 合并到 i+1 里
    // nums[i] > threshold / ( size[find(i + 1)] - 1)
    // 考虑nums[i]如果孤身一人或者nums[i]是一条链 那么nums[i]一定是最小的
    // 因为 我现在去合并 i 之前把i合并了的一定大于 nums[i]

    // 我们现在考虑合并 i,i+1
    // 如果 i+1是链  那么他的根就是最小的

    // 比较的是合并之后去掉最小的那个根。 nums[i] 就是整个链上最小的元素，
    // 所以 nums[i] > threshold / ( size[find(i + 1)] - 1)
    // 所以长为 size[find(i + 1)] - 1 的子数组是合法的
    public int validSubarraySize(int[] nums, int threshold) {
        int[] ids = IntStream
                .range(0, nums.length)
                .boxed()
                .sorted((i, j) -> nums[j] - nums[i])
                .mapToInt(k -> k)
                .toArray();

        for (int i : ids) {
            int j = find(i + 1);
            p[i] = j;
            size[j] += size[i];
            if (nums[i] > threshold / (size[j] - 1))
                return size[j] - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        元素值大于变化阈值的子数组 s = new 元素值大于变化阈值的子数组();
        int[] nums = {1, 4, 2};
        System.out.println(s.validSubarraySize(nums, 6));
    }
}
